Since the early 1990's, the World Wide Web (the “web”) has grown exponentially to include billions of web pages. Web analytics is the collection and analysis of web data in order to optimize user experiences and the usage of the web. The application of web analytics can help providers and content developers understand the dynamics of the web and gain insights into how visitors interact with their websites. For example, such knowledge can improve the relevance of information on a page that is returned in response to a search query or may increase the likelihood of converting page visitors into customers in commercial settings.
In particular, analysis of the structure of the web when modeled as a web graph has improved web searching. Web graph analysis typically involves the study of the patterns of links between web pages through the application of graph theory in which the links represent edges and the pages represent nodes in the graph. Well known canonical link analysis web graph algorithms such as the HITS (HyperLink Inducted Topic Search), PageRank, and SALSA (Stochastic Approach for Link-Structure Analysis) algorithms identify the dominant eigenvector of a non-negative matrix that describes the link structure of a given network of pages and use the values of the eigenvector to assign weights to each page. The weights can then be used to rank the pages. Page ranking is typically used to infer the importance of a page on the web and is one of the factors that are commonly considered when returning results to a search query.
Compression schemes are commonly utilized to significantly reduce the number of bits-per-edge required to losslessly represent web graphs. Such compression can help reduce the memory, storage, and processor requirements when analyzing the graphs. In addition, use of compression can reduce the runtime of an algorithm which is generally desirable. However, many popular web graph algorithms are not able to run directly on compressed graphs. One approach to deal with this limitation is to decompress the compressed graph on the fly prior to application of the algorithm. While this technique can provide satisfactory results in some cases, it is generally sub-optimal because the decompression step represents an additional computational burden.
This Background is provided to introduce a brief context for the Summary and Detailed Description that follow. This Background is not intended to be an aid in determining the scope of the claimed subject matter nor be viewed as limiting the claimed subject matter to implementations that solve any or all of the disadvantages or problems presented above.